/*
 * @lc app=leetcode.cn id=33 lang=golang
 * @lcpr version=30118
 *
 * [33] 搜索旋转排序数组
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func search(nums []int, target int) int {
	k := rotatePoint(nums)

	if k == 0 {
		return binarySearch(nums, target, 0, len(nums)-1)
	}

	if target >= nums[0] {
		return binarySearch(nums, target, 0, k-1)
	} else {
		return binarySearch(nums, target, k, len(nums)-1)
	}
}

func binarySearch(nums []int, target int, left int, right int) int {
	l, r := left, right
	for l < r {
		mid := (l + r) / 2

		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	if l == r && nums[l] == target {
		return l
	}
	return -1
}

func rotatePoint(nums []int) int {
	if len(nums) <= 1 {
		return 0
	}

	l, r := 0, len(nums)-1

	if nums[l] < nums[r] {
		// 没有翻转
		return 0
	}

	for nums[r] < nums[l] && l+1 < r {
		mid := (l + r) / 2
		if nums[mid] > nums[l] {
			// mid 在翻转点的左侧
			l = mid
		} else if nums[mid] == nums[l] {
			// 此时有 l == mid == r - 1, do nothing
		} else {
			// nums[mid] < nums[l]
			// mid 在翻转点的右侧
			r = mid
		}
	}

	// l == r 或者 l == r - 1
	if l == r {
		return l
	} else {
		return r
	}
}

// @lc code=end

/*
// @lcpr case=start
// [4,5,6,7,0,1,2]\n0\n
// @lcpr case=end

// @lcpr case=start
// [4,5,6,7,0,1,2]\n3\n
// @lcpr case=end

// @lcpr case=start
// [1]\n0\n
// @lcpr case=end

*/

